
%----------------------
%      原根与指数
%----------------------

%\chapter{原根与指数}
本章讨论同余方程$x^n \equiv a(mod\ m)$在什么条件下有解，在讨论过程中引入原根和指数的概念，通过讨论，对某些特殊的m有解的条件利用指数表达出来。\cite{min2003}\par

\section{次数(order)}

\subsection{基本概念}
\begin{definition}{次数(order)}
	设m是大于1的整数，a是与m互素的整数，使$a^l \equiv 1 (mod \ m)$成立的最小正整数$l$叫做a对模m的次数，记作$ord_m (a)$或$\delta_m (a) $。
\end{definition}

对于任意大于1的整数m，我们可以知道$ord_m(1)=1,ord_m(-1)=2$.

\vspace{1cm}
\begin{example}\\
	求$ord_{11} (a),$其中$a=1,2,3 \ldots,10$.
\end{example}
\begin{solution}
	我们可以把所有可能列出来，从而进行解答。\\
	\begin{center}	
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
			\hline 
			& a=1 & a=2 & a=3 & a=4 & a=5 & a=6 & a=7 & a=8 & a=9 & a=10 \\ 
			\hline 
			$a^1(mod \ 11)$& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 
			\hline 
			$a^2(mod \ 11)$& 1 & 4 & 9 & 5 & 3 & 3 & 5 & 9 & 4 & 1 \\ 
			\hline 
			$a^3(mod \ 11)$& 1 & 8 & 5 & 9 & 4 & 7 & 2 & 6 & 3 &  \\ 
			\hline 
			$a^4(mod \ 11)$& 1 & 5 & 4 & 3 & 9 & 9 & 3 & 4 & 5 &  \\ 
			\hline 
			$a^5(mod \ 11)$& 1 & 10 & 1 & 1 & 1 & 10 & 10 & 10 & 1 &  \\ 
			\hline 
			$a^6(mod \ 11)$& 1 & 9 &  &  &  & 5 & 4 & 3 &  &  \\ 
			\hline 
			$a^7(mod \ 11)$& 1 & 7 &  &  &  & 8 & 6 & 2 &  &  \\ 
			\hline 
			$a^8(mod \ 11)$& 1 & 3 &  &  &  & 4 & 9 & 5 &  &  \\ 
			\hline 
			$a^9(mod \ 11)$& 1 & 6 &  &  &  & 2 & 8 & 7 &  &  \\ 
			\hline 
			$a^{10}(mod \ 11)$& 1 & 1 &  &  &  & 1 & 1 & 1 &  &  \\ 
			\hline 
		\end{tabular} 
	\end{center}
	由上表可知$ord_{11}(1)=1,ord_{11}(2)=10,ord_{11}(3)=5,ord_{11}(4)=5,ord_{11}(5)=5,ord_{11}(6)=10,ord_{11}(7)=10,ord_{11}(8)=10,ord_{11}(9)=5,ord_{11}(10)=2$。
\end{solution}
\par
\vspace{1cm}

在次数定义时，只考虑与m互素的整数a，如果a和m不互素，不可能存在一个正整数$l$,使得$a^l \equiv 1 (mod \space m)(l \geq 1)$,所以通常只要谈到a对模m的次数，隐含条件都是a和m互素。
\par
\begin{SageMath}{a与m不互素时，不存在次数}
	\begin{verbatim}
		sage: a=5
		....: m=15
		....: for l in range(20):
		....:   print a,"^",l,"=",mod(a^l,m),"(mod ",m,")"
		....:
		5 ^ 0 = 1 (mod  15 )
		5 ^ 1 = 5 (mod  15 )
		5 ^ 2 = 10 (mod  15 )
		5 ^ 3 = 5 (mod  15 )
		5 ^ 4 = 10 (mod  15 )
		5 ^ 5 = 5 (mod  15 )
		5 ^ 6 = 10 (mod  15 )
		5 ^ 7 = 5 (mod  15 )
		5 ^ 8 = 10 (mod  15 )
		5 ^ 9 = 5 (mod  15 )
		5 ^ 10 = 10 (mod  15 )
		5 ^ 11 = 5 (mod  15 )
		5 ^ 12 = 10 (mod  15 )
		5 ^ 13 = 5 (mod  15 )
		5 ^ 14 = 10 (mod  15 )
		5 ^ 15 = 5 (mod  15 )
		5 ^ 16 = 10 (mod  15 )
		5 ^ 17 = 5 (mod  15 )
		5 ^ 18 = 10 (mod  15 )
		5 ^ 19 = 5 (mod  15 )
		sage:
		
	\end{verbatim}
\end{SageMath}
\subsection{次数性质和计算}
那么如何计算某个整数对某个模的次数呢？

\begin{theorem}{}{fubi}
	n为非负整数，$a^n \equiv 1 (mod \  m) \Leftrightarrow ord_m (a) \mid n$
\end{theorem}

\begin{theorem}{\cite{min2003}}{fubi}
	$a^0,a^1,\ldots,a^{ord_m(a)-1}$对模m两两不同余，其中$a^0=1$.
\end{theorem}

\begin{theorem}{\cite{min2003}}{fubi}
	若a对模m的指数是$\delta$,则$a^\gamma \equiv a^{\gamma '}(mod\ m)$成立的充要条件是$\gamma \equiv \gamma ' (mod\ \delta)$,特别地，$a^\gamma \equiv 1 (mod\ m) \Leftrightarrow \delta \mid \gamma$.
\end{theorem}

\begin{theorem}{次数性质\cite{jia2017}}{fubi}\label{thm:orderproperty}
	设a对模m的次数是$ord_m (a)$，则有：\\
	(1)$ord_m (a) \mid \varphi (m)$;\\
	(2)$b \equiv a (mod\  m) \Rightarrow ord_m (b) = ord_m (a)$.
\end{theorem}
利用上面的次数性质，可以再求次数时减少计算量。
\begin{example}\\
	计算5对模17的次数。
\end{example}
\begin{solution}\\
	由于$\varphi(17)=16$，根据次数性质~\ref{thm:orderproperty},次数可以被$\varphi(17)$整除(也就是16的因子)，而16的因子有1，2，4，8，16，所以只需计算5的1，2，4，8，16次方：\\
	\begin{center}
		$5^1 \equiv 5 (mod\  17)$\\
		$5^2 \equiv 10 (mod\  17)$\\
		$5^4 \equiv 13 (mod\  17)$\\
		$5^8 \equiv 16 (mod\  17)$\\
		$5^{16} \equiv 1 (mod\  17)$\\
	\end{center}
可见$ord_{17} (5)=16$.
\end{solution}
\par

\begin{theorem}{幂的周期性\cite{jia2017}}{fubi}
	s,t是任意非负整数，$a^s \equiv a^t (mod \  m) \Leftrightarrow s \equiv t (mod \  ord_m (a)) $
\end{theorem}
以上定理揭示了一个事实，当$m > 1,gcd(a,m)=1,$序列$a^i (mod \  m) \  (i=1,2,3,\ldots)$是周期序列,周期为$ord_m(a)$。
\begin{example}\\
	我们先看$5^x (mod \  12)$序列的周期性，我们知道$ord_{12}(5)=2$:\\
	\begin{SageMath}{幂的周期性示例}
		\begin{verbatim}
			sage: a=5
			....: m=12
			....: for l in range(50):
			....: ^Iprint a,"^",l,"=",mod(a^l,m),"(mod ",m,")"
			....:
			5 ^ 0 = 1 (mod  12 )
			5 ^ 1 = 5 (mod  12 )
			5 ^ 2 = 1 (mod  12 )
			5 ^ 3 = 5 (mod  12 )
			5 ^ 4 = 1 (mod  12 )
			5 ^ 5 = 5 (mod  12 )
			5 ^ 6 = 1 (mod  12 )
			5 ^ 7 = 5 (mod  12 )
			5 ^ 8 = 1 (mod  12 )
			5 ^ 9 = 5 (mod  12 )
			5 ^ 10 = 1 (mod  12 )
			5 ^ 11 = 5 (mod  12 )
			5 ^ 12 = 1 (mod  12 )
			5 ^ 13 = 5 (mod  12 )
			5 ^ 14 = 1 (mod  12 )
			5 ^ 15 = 5 (mod  12 )
			5 ^ 16 = 1 (mod  12 )
			5 ^ 17 = 5 (mod  12 )
			5 ^ 18 = 1 (mod  12 )
			5 ^ 19 = 5 (mod  12 )
			5 ^ 20 = 1 (mod  12 )
			5 ^ 21 = 5 (mod  12 )
			5 ^ 22 = 1 (mod  12 )
			5 ^ 23 = 5 (mod  12 )
			5 ^ 24 = 1 (mod  12 )
			5 ^ 25 = 5 (mod  12 )
			5 ^ 26 = 1 (mod  12 )
			5 ^ 27 = 5 (mod  12 )
			5 ^ 28 = 1 (mod  12 )
			5 ^ 29 = 5 (mod  12 )
			5 ^ 30 = 1 (mod  12 )
			5 ^ 31 = 5 (mod  12 )
			5 ^ 32 = 1 (mod  12 )
			5 ^ 33 = 5 (mod  12 )
			5 ^ 34 = 1 (mod  12 )
			5 ^ 35 = 5 (mod  12 )
			5 ^ 36 = 1 (mod  12 )
			5 ^ 37 = 5 (mod  12 )
			5 ^ 38 = 1 (mod  12 )
			5 ^ 39 = 5 (mod  12 )
			5 ^ 40 = 1 (mod  12 )
			5 ^ 41 = 5 (mod  12 )
			5 ^ 42 = 1 (mod  12 )
			5 ^ 43 = 5 (mod  12 )
			5 ^ 44 = 1 (mod  12 )
			5 ^ 45 = 5 (mod  12 )
			5 ^ 46 = 1 (mod  12 )
			5 ^ 47 = 5 (mod  12 )
			5 ^ 48 = 1 (mod  12 )
			5 ^ 49 = 5 (mod  12 )
			sage:
			
		\end{verbatim}
	\end{SageMath}
\end{example}

\section{原根(primitive root)}

\subsection{基本概念}
\begin{definition}{原根(primitive root)}
	设m是大于1的整数，a是与m互素的整数，如果$ord_m (a) = \varphi (m)$，则a称为m的原根。
\end{definition}

设a对模m的次数为l，符号化描述为$ord_m(a)=l$,欧拉函数 $\varphi (m)$表示完全剩余系中与m互素的元素个数。也就是说欧拉函数只和m有关，而次数与m和a有关。\par
\cite{min2003}中对原根的定义为：若a对模m的次数\footnote{在闵先生的原书中称为指数，把本书中的指数称为指标，这是对英文的不同翻译造成的。}是$\varphi(m)$,则a叫做模m的一个原根。\par

\begin{example}\\
	5是否是6的原根？是否是8的原根？
\end{example}
\begin{solution}\\
	5,6互素，已知
	$\varphi(6)=2$,且$5^1 \equiv 5 \pmod{6},5^2 \equiv 1 \pmod{6}$
	,得$ord_6(5)=2$,所以$ord_6(5)=\varphi(6)$,由定义可知 \uwave{5是6的原根} 。\\
	由于5，8互素，$\varphi(8)=4$,且$5^1 \equiv 5 \pmod{8},5^2 \equiv 1\pmod{8}$,得$ord_8(5)=2$,所以$ord_8(5) \neq \varphi(8)$,由定义可知\uuline{5不是8的原根}。
\end{solution}

\subsection{原根的等价概念}
\begin{theorem}{原根充要条件}{fubi}\label{thm:prirootreduce}
	$ord_m(a)=\varphi(m) \Leftrightarrow 1,a,a^2,\ldots,a^{\varphi(m)}$是模m的一个缩系。\\
	也可叙述为：a是m原根的充要条件是$1,a,a^2,\ldots,a^{\varphi(m)}$是模m的一个缩系。
\end{theorem}

\begin{theorem}{原根充要条件}{fubi}
	a是m的一个原根，t是非负整数，则$a^t$也是m的原根的充要条件是$gcd(t,\varphi(m))=1$。
\end{theorem}


\subsection{原根存在性判断}
对于任意模数m，不一定存在原根。所以探讨什么情况下原根存在是有意义的。\\
\begin{theorem}{奇素数原根存在性\cite{jia2017}}{fubi}
	设p是奇素数，则p的原根存在。
\end{theorem}

\begin{theorem}{奇素数次幂原根存在性\cite{jia2017}}{fubi}
	设p是奇素数，则对于任意正整数$l$，存在$p^l$的原根。
\end{theorem}

\begin{theorem}{奇素数次幂倍数原根存在性\cite{jia2017}}{fubi}
	设p是奇素数，则对于任意正整数$l$，存在$2p^l$的原根。
\end{theorem}

\begin{theorem}{无原根整数\cite{jia2017}}{fubi}
	设a是一个奇数，则对任意整数$k \geq 3$,有$a^{\frac{1}{2} \varphi(2^k)} \equiv a^{2^{k-2}} \equiv 1 (mod \  2^k)$,即$2^k (k \geq 3)$没有原根。
\end{theorem}
有了上面这些定理，可以推出原根存在的充要条件。
\begin{theorem}{原根存在性判定\cite{jia2017}}{fubi}
	设m是大于1的整数，则m的原根存在的充要条件是m为2，4，$p^l,2p^l$之一，其中$l \geq 1$,p为奇素数。
\end{theorem}

\subsection{原根的计算}
上面我们讨论了原根的存在性判定，还有两个重要问题就是判定有几个原根和这几个原根是什么。\par

\begin{theorem}{\cite{jia2017}}{fubi}
	设m是大于2的整数，$\varphi(m)$的所有不同的素因子是$q_1,q_2,\ldots,q_s$,则与m互素的正整数g是m的一个原根的充要条件是$g^{\frac{\varphi(m)}{q_1}} \nequiv 1 (mod \  m),i=1,2,\ldots,s$。
\end{theorem}

\begin{example}\cite{jia2017}\\
	求41的原根。
\end{example}
\begin{solution}\\
	$\varphi (m)=\varphi(41)=40=2^3 \times 5$,所以$\varphi(m)$的素因子是$q_1 = 5, q_2 =2$，可计算得:\\
		\begin{center}
			$\frac{\varphi(m)}{q_1} =\frac{40}{5}=8,\frac{\varphi(m)}{q_2}=\frac{40}{2}=20$
		\end{center}
	
	与m互素的正整数g=2,3,4,5,6，分别验算$g^8,g^{20}$,得:\\
	$2^8 \equiv 10 (mod \  41),2^{20} \equiv 1 (mod \  41)$,不符合原根条件;\\
	$3^8 \equiv 1 (mod \  41)$,不符合原根条件;\\
	$4^8 \equiv 18 (mod \  41),2^{20} \equiv 1 (mod \  41)$,不符合原根条件;\\
	$5^8 \equiv 10 (mod \  41),2^{20} \equiv 1 (mod \  41)$,不符合原根条件;\\
	$6^8 \equiv 10 (mod \  41),2^{20} \equiv 40 (mod \  41)$,符合原根条件;\\
	t遍历$\varphi(m)=40$的缩系${1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39},6^t$遍历41的原根,可得：\\
	$6^1 \equiv 6 (mod \  41);6^3 \equiv 11 (mod \  41);6^7 \equiv 29 (mod \  41);$\\
	$6^9 \equiv 19 (mod \  41);6^{11} \equiv 28 (mod \  41);6^{13} \equiv 24 (mod \  41);$\\
	$6^{17} \equiv 26 (mod \  41);6^{19} \equiv 34 (mod \  41);6^{21} \equiv 35 (mod \  41);$\\
	$6^{23} \equiv 30 (mod \  41);6^{27} \equiv 12 (mod \  41);6^{29} \equiv 22 (mod \  41);$\\
	$6^{31} \equiv 13 (mod \  41);6^{33} \equiv 17 (mod \  41);6^{37} \equiv 15 (mod \  41);$\\
	$6^{39} \equiv 7 (mod \  41);$\\
	所以，41的原根为:6,7,11,12,13,15,17,19,22,24,26,28,29,30,34,35
\end{solution}

\section{指数/离散对数}
“如果m是一个原根g，根据定理~\ref{thm:prirootreduce}可知，$1,g,g^2,\ldots,g^{\varphi(m)-1}$是模m的一个缩系，因此，对任何一个与m互素的整数a，存在唯一的非负整数r，$0 \leq r < \varphi(m)$,使得$g^r \equiv a(mod\ m)$,由于原根具有以上性质，我们可以给出下面的定义”。\cite{jia2017}(第103页)\par
\begin{definition}{指数(index)\cite{jia2017}}{fubi}
	设m是大于1的整数，g是m的一个原根，a是与m互素的整数，则存在唯一的非负整数r，$0 \leq r < \psi(m)$，满足$a \equiv g^r (mod \ m)$，称r为以g为底a对模m的指数,记作$ind_g a$,$a \equiv g^{ind_g a} (mod\ m)$,有时也把指数称为离散对数，记为$log_g a,a\equiv g^{log_g a}(mod\ m)$。
\end{definition}

\begin{remark}
	对于实数来说$a^c=b \rightarrow \log_a b =c$,c叫做以a为底b的对数（logarithm）。所以我们通常也把$ind_g a$叫做离散对数，记作$\log_g a$.
\end{remark}
离散对数的计算问题是一个计算上困难的问题，目前没有找到一个有效的算法。
\begin{example}\\
	m=7，有原根g=3，计算指数表。
\end{example}
\begin{solution}\\
	$3^x \equiv a (mod \  7)$,可知x和a的关系为：\\
	$x=1,a=3^1=3 \equiv 3 (mod \  7)$\\
	$x=2,a=3^2=9 \equiv 2 (mod \  7)$\\
	$x=3,a=3^3=27 \equiv 6 (mod \  7)$\\
	$x=4,a=3^4=81 \equiv 4 (mod \  7)$\\
	$x=5,a=3^5=243 \equiv 5 (mod \  7)$\\
	$x=6,a=3^6=729 \equiv 1 (mod \  7)$\\
	整理以上计算结果，可得指数表。
\end{solution}

\begin{theorem}{原根的幂}{fubi}
	g是m的一个原根，$g^x \equiv g^y (mod \  m) \Leftrightarrow x \equiv y (mod \  \varphi(m))$
\end{theorem}

\begin{theorem}{原根的次数}{fubi}
	g是m的一个原根，整数a,b均与m互素，$a \equiv b (mod \  m) \Leftrightarrow ind_g a \equiv ind_g b (mod \  \varphi(m))$
\end{theorem}

可见离散指数与实数中的指数的性质很相似，我们可以利用原根做出指数表。

\begin{example}\cite{jia2017}\\
	做出模41的指数表
\end{example}
\begin{solution}\\
	已知6是41的一个原根，所以g=6，又知$\varphi(41)=40$，直接计算$g^r (mod \  m),g=6,m=41,r=0,1,\ldots,39$:(下表中中的值为$6^{a+b} (mod\ 41),a \in \{0,1,2,3,4,5\},b \in \{0,6,12,18,24,30,36\}$)\\
	\begin{center}
		\begin{tabular}{|c|c|c|c|c|c|c|}
			\hline
		\rowcolor{gray!40}	& a=0& a=1 & a=2 & a=3 & a=4 & a=5 \\ 
			\hline 
			b=0& $6^{(a+b)} \equiv 1(mod\ 41)$ & 6 & 36 & 11 & 25 & 27 \\ 
			\hline 
			b=6& 39&29  &10  & 19 &32  & 28 \\ 
			\hline 
			b=12&4 & 24 & 21 & 3 &18  & 26 \\ 
			\hline 
			b=18& 33&  34& 40 &35  & 5 & 30 \\ 
			\hline 
			b=24& 16&14  &  2& 12 & 31 & 22 \\ 
			\hline 
			b=30&9 & 13 & 37 & 17 & 20 & 38  \\ 
			\hline 
			b=36& 23&15  & 8 & 7 & - & - \\ 
			\hline 
		\end{tabular}
	\end{center}
	 
	\par
	根据计算结果，我们构造指数表，第一行表示$g^r (mod \  m)$的个位数，第一列表示$g^r (mod \  m)$的十位数，交叉位置即为r：\\
	\begin{center}
		\emph{模41的指数表}\\
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
			\hline 
			\rowcolor{gray!40}& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 
			\hline 
			0& - & 0 & 26 & 15 & 12 & 22 & 1 & 39 &38& 30 \\ 
			\hline 
			1& 8 & 3 & 27 & 31 & 25 & 37 & 24 & 33 &16 & 9\\ 
			\hline 
			2&34  & 14 & 29 & 36 & 13 & 4 & 17 & 5 &11 &7 \\ 
			\hline 
			3& 23 & 28 & 10 & 18 & 19 & 21 &2  & 32 &35 & 6\\ 
			\hline 
			4& 20 & - & - & - & - & - & - & - &- &- \\ 
			\hline 
		\end{tabular}
	\end{center}
		 
\end{solution}

\section{n次剩余}
\begin{definition}{n次剩余}
	设m是大于1的整数，a是与m互素的整数，若$n(n \geq 2)$次同余方程$x^n \equiv a (mod \ m)$有解，则把a称为模m的n次剩余，否则（无解），a叫作模m的n次非剩余。
\end{definition}

\begin{theorem}{高次同余方程有解充要条件}{fubi}
	g是m的一个原根，a是与m互素的整数，则同余方程$x^n \equiv a (mod \ m)$有解$\Leftrightarrow gcd(n,\varphi(m)) \mid ind_g a$,且解的个数为$gcd(n,\varphi(m))$.
\end{theorem}

\begin{example}\\
	求解同余方程$x^{12} \equiv 37 (mod \ 41)$.
\end{example}
\begin{solution}\\
	$\varphi(41)=40,gcd(12,40)=4$，查模41的指数表，知$ind_g 37 =32$,所以$4 \mid 32$，可知同余方程有解。\\
	原同余方程与$12ind_g x \equiv ind_g 37 = 32 (mod \ 40)$等价,有$3ind_g x \equiv 8 (mod \ 10)$,3模10的逆元是7，两边同乘7，得到$ind_g x \equiv 56 \equiv 6 (mod \ 10)$,可解得$ind_g x  \equiv 6,16,26,36 (mod \ 40)$,通过查模41的指数表可得到原同余方程的解为$x \equiv 39,18,2,23 (mod \ 41)$.
\end{solution}
